class Solution:
    def combinationSum(self, candidates, target):
        if target < 0 or len(candidates) == 0:
            return []
        if target == 0:
            return [[]]
        withFirst = [
            [candidates[0]] + x
            for x in self.combinationSum(candidates, target - candidates[0])
        ]
        withoutFirst = self.combinationSum(candidates[1:], target)
        return withFirst + withoutFirst


s = Solution()
print(s.combinationSum([2, 3, 6, 7], 7))
print(s.combinationSum([2, 3, 5], 8))
